package top.minuy.structure.graph.path.bfs;

import top.minuy.res.graph.GraphRes;
import top.minuy.structure.graph.representations.table.Graph;

import java.util.Random;

/**
 * 广度优先遍历路径问题测试
 *
 * @author Minuy
 * @time 0:36
 * @date 2021/11/20
 */
public class Test {
    public static void main(String[] args) {
        Graph graph = new Graph(GraphRes.G_BFS_2);

        System.out.println("单路径规划 : ");
        SingleSourcePath ssp = new SingleSourcePath(graph, 0);
        System.out.println("0 -> 4 : " + ssp.path(4));
        System.out.println("0 -> 6 : " + ssp.path(6));
        System.out.println("0 -> 7 : " + ssp.path(7));

        System.out.println("多路径规划 : ");
        AllPairsPath app = new AllPairsPath(graph);
        System.out.println("4 -> 6 : " + app.path(4, 6));
        System.out.println("4 -> 0 : " + app.path(4, 0));
        System.out.println("7 -> 2 : " + app.path(7, 2));

        System.out.println("随机执行多路径规划 : ");
        int n = 10;
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            int s = random.nextInt(graph.V());
            int t = random.nextInt(graph.V());
            System.out.println(String.format("%d -> %d : ", s, t) + app.path(s, t));
        }

        System.out.println("优化单路径规划 : ");
        Path path1 = new Path(graph, 0, 5);
        System.out.println("0 -> 5 : " + path1.path());
        Path path2 = new Path(graph, 4, 5);
        System.out.println("4 -> 5 : " + path2.path());
        Path path3 = new Path(graph, 0, 7);
        System.out.println("0 -> 7 : " + path3.path());

        System.out.println("无权单源最短路径 : ");
        USSSPath USSSPath1 = new USSSPath(graph, 0);
        System.out.print("0 -> 5 : " + USSSPath1.path(5));
        System.out.println(", dis = " + USSSPath1.dis(5));
        USSSPath USSSPath2 = new USSSPath(graph, 1);
        System.out.print("1 -> 4 : " + USSSPath2.path(4));
        System.out.println(", dis = " + USSSPath2.dis(4));
        USSSPath USSSPath3 = new USSSPath(graph, 4);
        System.out.print("4 -> 7 : " + USSSPath3.path(7));
        System.out.println(", dis = " + USSSPath3.dis(7));
    }
}
